package com.cuz.daileetcode.bat100;

/***
 * 超级水王问题：给你一个数组，
 * 出现次数大于数组长度的一半的元素称之为水王数，
 * 怎么能快速找到水王数？
 *
 * 内存限制：时间复杂度O(n)，额外空间复杂度O(1)
 * ——也就是遍历数组的次数为有限次，申请的变量数为有限个
 */
public class 超级水王问题 {


    public static int waterKing(int[] arr) {
        Integer candidate = null;
        int hp = 0;
        for (int i = 0; i < arr.length; i++) {
            int cur = arr[i];
            if (candidate == null) {
                candidate = cur;
                hp = 1;
            } else if (candidate == cur) {
                hp++;
            } else {
                hp--;
                if (hp == 0) {
                    candidate = null;
                }
            }
        }
        if (hp == 0) {
            return -1;
        }
        int candidateOccurrences = 0;
        for (int i : arr) {
            if (i == candidate) {
                candidateOccurrences++;
            }
        }
        if (candidateOccurrences > arr.length / 2) {
            return candidate;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ints = {2, 3,2, 1, 1, 1};
        System.out.println(waterKing(ints));
    }

}
